#ifndef _SGF_LIST_H_
#define _SGF_LIST_H_

#include "Type.h"

namespace SGF
{
	template <class T>
	class List
	{
	private:
		template <class N>
		struct Node
		{
			N value;
			Node<N>* next;
			Node<N>* previous;
			Node()
			{
				next = NULL;
				previous = NULL;
			}

			Node(const N& src)
			{
				value = src;
				next = NULL;
				previous = NULL;
			}
			Node(const Node<N>& src)
			{
				next = src.next;
				previous = src.previous;
				value = src.value;
			}

			Node<N>& operator=(const Node<N>& src)
			{
				next = src.next;
				previous = src.previous;
				value = src.value;
				return*this;
			}
		};
		Node<T>* _begin;
		Node<T>* _end;
		UInt64 _size;
	public:
		List();
		List(const List<T>& src);
		List<T>& operator=(const List<T>& src);
		~List();
		T& operator[](UInt64 i);
		void Add(T src);
		void Insert(UInt64 pos, T src);
		void Remove(T src);
		void RemoveIndex(UInt64 i);
		T& GetFirst();
		T& GetLast();
		void Clear();
		UInt64 GetSize();
		void SetSize(UInt64 i);
		void Print();
	};

	template <class T>
	SGF::List<T>::List()
	{
		_size = 0;
		_begin = NULL;
		_end = NULL;
	}

	template <class T>
	SGF::List<T>::List(const List<T>& src)
	{
		_size = 0;
		_begin = NULL;
		_end = NULL;
		if (src._size == 0)
		{
			_size = 0;
			_begin = NULL;
			_end = NULL;
		}
		else
		{
			Node<T>* iterator = src._begin;
			while (iterator != NULL)
			{
				Add(iterator->value);
				iterator = iterator->next;
			}
			_size = src._size;
		}		
	}

	template <class T>
	List<T>& SGF::List<T>::operator=(const List<T>& src)
	{
		Clear();
		if (src._size == 0)
		{
			_size = 0;
			_begin = NULL;
			_end = NULL;
		}
		else
		{
			Node<T>* iterator = src._begin;
			while (iterator != NULL)
			{
				Add(iterator->value);
				iterator = iterator->next;
			}
			_size = src._size;
		}		
		return*this;
	}

	template <class T>
	SGF::List<T>::~List()
	{
		if (_size != 0)
		{
			Node<T>* iterator = _begin;
			while (iterator != NULL)
			{
				Node<T>* temp = iterator;
				iterator = iterator->next;
				delete[] temp;
			}
		}
	}

	template <class T>
	T& SGF::List<T>::operator[](UInt64 i)
	{
		if ((_size > 0) && (i < _size))
		{
			UInt64 counter = 0;
			Node<T>* iterator = _begin;
			while (counter != i)
			{
				iterator = iterator->next;
				counter++;
			}
			return iterator->value;
		}
		else throw 10;
	}

	template <class T>
	void SGF::List<T>::Add(T src)
	{
		T newSrc = src;
		if (_size == 0)
		{
			_begin = new Node<T>(src);
			_end = _begin;
			_size = 1;
		}
		else
		{
			_size++;
			Node<T>* node = new Node<T>(src);
			_end->next = node;
			node->previous = _end;
			_end = node;
		}
	}

	template <class T>
	void SGF::List<T>::Insert(UInt64 pos, T src)
	{
		if (_size == 0)
		{
			if (pos == 0)
			{
				_begin = new Node<T>(src);
				_end = _begin;
				_size = 1;			
			}
		}
		else
		{
			if (pos < _size)
			{
				if (pos == 0)
				{
					_size++;
					Node<T>* newNode = new Node<T>(src);
					_begin->previous = newNode;
					newNode->next = _begin;
					_begin = newNode;
				}
				else
				{
					_size++;
					Node<T>* iterator = _begin;
					UInt64 counter = 0;
					while (counter != pos)
					{
						counter++;
						iterator = iterator->next;
					}
					Node<T>* newNode = new Node<T>(src);
					newNode->next = iterator;
					newNode->previous = iterator->previous;
					iterator->previous->next = newNode;
					iterator->previous = newNode;
				}
			}
		}
	}

	template <class T>
	void SGF::List<T>::Remove(T src)
	{
		if (_size > 0)
		{
			Node<T>* iterator = _begin;
			while ((iterator != NULL) && (iterator->value != src))
			{
				iterator = iterator->next;
			}
			if (iterator != NULL)
			{
				if (_size == 1)
				{
					delete iterator;
					_size = 0;
					_begin = NULL;
					_end = NULL;
				}
				else
				{
					_size--;
					if (iterator == _begin)
					{
						_begin = iterator->next;
						_begin->previous = NULL;
						delete iterator;
						return;
					}
					if (iterator == _end)
					{
						_end = iterator->previous;
						_end->next = NULL;
						delete iterator;
						return;
					}
					iterator->next->previous = iterator->previous;
					iterator->previous->next = iterator->next;
					delete iterator;
				}
			}
		}
	}

	template <class T>
	void SGF::List<T>::RemoveIndex(UInt64 i)
	{
		if ((_size > 0) && (i < _size))
		{
			Node<T>* iterator = _begin;
			UInt64 counter = 0;
			while (counter != i)
			{
				counter++;
				iterator = iterator->next;
			}
			_size--;
			if (iterator->next != NULL)
			{
				iterator->next->previous = iterator->previous;
			}
			else
			{
				_end = iterator->previous;
			}
			if (iterator->previous != NULL)
			{
				iterator->previous->next = iterator->next;
			}
			else
			{
				_begin = iterator->next;
			}
			delete iterator;
		}
	}

	template <class T>
	T& SGF::List<T>::GetFirst()
	{
		if (_begin != NULL)
		{
			return _begin->value;
		}
	}

	template <class T>
	T& SGF::List<T>::GetLast()
	{
		if (_end != NULL)
		{
			return _end->value;
		}
	}

	template <class T>
	void SGF::List<T>::Clear()
	{
		if (_size != 0)
		{
			Node<T>* iterator = _begin;
			while (iterator != NULL)
			{
				Node<T>* temp = iterator;
				iterator = iterator->next;
				delete[] temp;
			}
		}
		_begin = _end = NULL;
		_size = 0;
	}

	template <class T>
	UInt64 SGF::List<T>::GetSize()
	{
		return _size;
	}

	template <class T>
	void SGF::List<T>::SetSize(UInt64 i)
	{
		if (i == 0)
		{
			Clear();
			return;
		}
		if ((i > 0) && (i != _size))
		{
			if (i < _size)
			{
				_size = i;
				UInt64 counter = 0;
				Node<T>* iterator = _begin;
				while (counter != i)
				{
					iterator = iterator->next;
					counter++;
				}
				_end = iterator->prev;
				iterator->prev->next = NULL;
				while (iterator != NULL)
				{
					Node<T>* temp = iterator;
					iterator = iterator->next;
					delete temp;
				}
			}
			else
			{
				_size = i;
				for (UInt64 j = 0; j < i - _size; j++)
				{
					T val;
					Add(val);
				}
			}
		}
	}

}
#endif